package datastructure.list;

import java.lang.reflect.Array;

/**
 * Description：带头节点（不存储数据）的循环双链表，jdk1.8之前的版本
 * Author: zhangc
 * Date：2017/6/8 20:05
 */
public class LinkedList<T> implements List<T>, Iterable<T> {

    private Entry<T> header = new Entry<>(null, null, null);
    private int size = 0;

    private static class Entry<T> {
        T element;
        Entry<T> previous;
        Entry<T> next;

        private Entry(T element, Entry<T> previous, Entry<T> next) {
            this.element = element;
            this.previous = previous;
            this.next = next;
        }

    }

    public LinkedList() {
        header.previous = header.next = header;
    }

    private void addFirst(T element) {
        if (size == 0) {
            /*和JDK内部相同，JDK内部头结点不存储数据*/
            Entry<T> entry = new Entry<>(element, header, header);
            header.previous = header.next = entry;
            size++;
        }
    }

    @Override
    public void append(T element) {
        if (size == 0)
            addFirst(element);
        else {
            Entry<T> entry = new Entry<>(element, header.previous, header);
            header.previous.next = entry;
            header.previous = entry;
            size++;
        }
    }

    @Override
    public void insert(int index, T element) {

    }

    @Override
    public T get(int index) {
        if (indexSafe(index)) {
            Entry<T> entry = header;
            /*当下标大于列表一半长度时，从后开始查找*/
            if (index > (size >> 1)) {
                for (int i = size; i > index; --i) {
                    entry = entry.previous;
                }
                return entry.element;
            } else {
                for (int i = 0; i <= index; ++i) {
                    entry = entry.next;
                }
                return entry.element;
            }
        }
        throw new IllegalArgumentException("List 下标越界");
    }

    private boolean indexSafe(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("列表下标越界");
        }
        return true;
    }

    @Override
    public T remove(int index) {
        return null;
    }

    @Override
    public List<T> subList(int start, int end) {
        return null;
    }

    @Override
    public void clear() {

    }

    @Override
    public int length() {
        return size;
    }

    @Override
    public boolean contains(T element) {
        return false;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T[] toArray(T[] array) {
        Entry<T> entry = header.next;
        if (array.length < size) {
            array = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
        }
        for (int i = 0; i < size; i++) {
            array[ i ] = entry.element;
            entry = entry.next;
        }
        return array;
    }

    @Override
    public Object[] toArray() {
        Entry<T> entry = header;
        Object[] array = new Object[ length() ];
        for (int i = 0; i < length(); ++i) {
            array[ i ] = entry.element;
            entry = entry.next;
        }
        return array;
    }

    @Override
    public Iterator iterator() {
        return new Iterator();
    }

    private class Iterator implements java.util.Iterator<T> {
        private int index = 0;

        @Override
        public boolean hasNext() {
            return index < length();
        }

        @Override
        public T next() {
            return get(index++);
        }
    }

}
